package Algorithm.dynamicProgramming.introduct;

/**
 * 746. 使用最小花费爬楼梯 https://leetcode.cn/problems/min-cost-climbing-stairs
 * 题目简述：cost[i]是从楼梯第i个台阶向上爬需要支付的费用，支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
 * 注意根据示例审题，最后一个cost是一个台阶，要再上一层才是楼顶
 */
public class MinCostClimbingStairs {

    public static void main(String[] args) {
        new MinCostClimbingStairs().minCostClimbingStairs2(new int[]{10,15,20});
    }

    /**
     * 动态规划
     * 1. 定义dp[i]: 爬到第i级台阶的最小花费
     * 2. 确定递推公式：dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
     * 3. 初始化dp：dp[0] = 0;dp[1] = 0;
     * 4. 递推到楼顶，到楼顶的最小花费即为dp[n] = Math.min(dp[n-1]+cost[n-1], dp[n-2]+cost[n-2]);
     */
    public int minCostClimbingStairs(int[] cost) {
        int i = 2, dpi=0, dpi_1 = 0, dpi_2 = 0;
        for(;i <= cost.length;i++) {
            dpi = Math.min(dpi_1+cost[i-1], dpi_2+cost[i-2]);
            dpi_2 = dpi_1;
            dpi_1 = dpi;
        }
        return dpi;
    }

    /**
     * 动态规划
     * 1. 定义dp[i]: 爬到第i级台阶的最小花费
     * 2. 确定递推公式：dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
     * 到楼顶的最小花费即为Math.min(dp[n-2], dp[n-1])
     */
    public int minCostClimbingStairs2(int[] cost) {
        int p1 = cost[0], p2 = cost[1], r=0;
        for(int i = 2;i < cost.length;i++) {
            r = Math.min(p1, p2) + cost[i];
            p1 = p2;
            p2 = r;
        }
        return Math.min(p1, p2);
    }

}
